|
|
Automorphism Groups of Geometrically Represented Graphs
Zeman, Peter ; Klavík, Pavel (vedoucí práce) ; Nedela, Roman (oponent)
V tejto práci skúmame grupy automorfizmov grafov s vel'mi silnou štruktúrou. Pravdepodobne jeden z prvých výsledkov v tomto smere je Jordanova charakterizácia triedy grúp automorfizmov stromov T z roku 1869. Prekvapivo, grupy automorfizmov prienikových grafov boli študované iba vel'mi málo. Aj pre vel'mi pochopené triedy prienikových grafov, je štruktúra ich grúp auto- morfizmov neznáma. Hlavná otázka, ktorou sa zaoberáme je, či sa z dobrej znalosti reprezentácií prienikového grafu geometrických objektov dá zrekonštruovat' jeho grupa automorfizmov. V práci skúmame hlavne intervalové grafy. Intervalové grafy sú prienikové grafy intervalov na reálnej osi. Sú jednou z naj- starších a najviac študovaných tried prienikových grafov. Náš hlavný výsledok ho- vorí, že trieda grúp automorfizmov intervalových grafov I je rovnaká ako trieda grúp automorfizmov stromov T . Navyše ukazujeme postup ako pre daný intervalový graf skonštruovat' strom s rovnakou grupou automorfizmov a tak isto obrátene, pre daný strom skonštruujeme intervalový graf. 1
|
|
|
Průnikové reprezentace grafů
Töpfer, Martin ; Jelínek, Vít (vedoucí práce) ; Šámal, Robert (oponent)
Průnikový graf je graf, ve kterém mezi dvěma vrcholy vede hrana, právě když jim odpovídající objekty se protínají. Tato práce se zabývá průnikovými grafy L-útvarů (tzv. L-grafy) a jejich speciálním případem, kdy konce všech L-útvarů jsou na jedné přímce (tzv. vnějškovými L-grafy). Po přehledu, co platí o L-grafech, používáme podobné postupy na vnějškové L-grafy. Ukážeme, že intervalové grafy, tětivové grafy (circular graphs) a vnějškově rovinné grafy jsou vnějškové L-grafy. Poté charakterizujeme vnějškové L-grafy pomocí uspořádání vrcholů bez zakázaných vzorů. Powered by TCPDF (www.tcpdf.org)
|
|
|
Automorphism Groups of Geometrically Represented Graphs
Zeman, Peter ; Klavík, Pavel (vedoucí práce) ; Nedela, Roman (oponent)
V tejto práci skúmame grupy automorfizmov grafov s vel'mi silnou štruktúrou. Pravdepodobne jeden z prvých výsledkov v tomto smere je Jordanova charakterizácia triedy grúp automorfizmov stromov T z roku 1869. Prekvapivo, grupy automorfizmov prienikových grafov boli študované iba vel'mi málo. Aj pre vel'mi pochopené triedy prienikových grafov, je štruktúra ich grúp auto- morfizmov neznáma. Hlavná otázka, ktorou sa zaoberáme je, či sa z dobrej znalosti reprezentácií prienikového grafu geometrických objektov dá zrekonštruovat' jeho grupa automorfizmov. V práci skúmame hlavne intervalové grafy. Intervalové grafy sú prienikové grafy intervalov na reálnej osi. Sú jednou z naj- starších a najviac študovaných tried prienikových grafov. Náš hlavný výsledok ho- vorí, že trieda grúp automorfizmov intervalových grafov I je rovnaká ako trieda grúp automorfizmov stromov T . Navyše ukazujeme postup ako pre daný intervalový graf skonštruovat' strom s rovnakou grupou automorfizmov a tak isto obrátene, pre daný strom skonštruujeme intervalový graf. 1
|
|
|
Algoritmické problémy související s průnikovými grafy
Ivánek, Jindřich ; Pergel, Martin (vedoucí práce) ; Rytíř, Pavel (oponent)
V práci studujeme dva problémy pokrytí klikami, které mají zajímavé aplikace při reprezentaci tzv. k -bendovými průnikovými grafy: problém stupně pokrytí hran klikami a problém vrstevnatého pokrytí hran klikami. Zaměřujeme se na složitost těchto problémů a polynomiální algoritmy pro omezené třídy grafů. Hlavními výsledky práce je NP-úplnost problému vrstevnatého pokrytí hran klikami, polynomiální algoritmus pro tento problém na podtřídě grafů bez diamantů a také některé horní odhady pro konkrétní třídy grafů.
|
host ::
RSS.